package com.util.DataStructure;

import java.util.ArrayList;

/**
 * Created by wlc on 2018/6/10.
 * 孩子兄弟表示法
 */

public class Tree<T> {
    /**
     * 内部类
     */
    class Node {
        T  value;
        Node leftChild;
        Node rightChild;

        Node(T value) {
            this.value = value;
            leftChild  = null;
            rightChild = null;
        }

        public void display() {
            System.out.print(this.value + "\t");
        }

        @Override
        public String toString() {
            return String.valueOf(value);
        }
    }

    /**
     * 数据成员
     */
    private Node root = null;

    /**
     * 构造函数
     */
    Tree(T value) {
        root = new Node(value);
    }

    /**
     * 节点顺序插入操作
     * @param value 必须是数值型
     * @return 出错信息
     */
    public String sortInsert(T value) {
        String error = null;

        Node node = new Node(value);
        if (root == null) {
            root = node;
        } else {
            Node current = root;
            Node parent = null;
            while (true) {
                if (Double.valueOf(value.toString()) < Double.valueOf(current.value.toString())) {
                    parent = current;
                    current = current.leftChild;
                    if (current == null) {
                        parent.leftChild = node;
                        break;
                    }
                } else if (Double.valueOf(value.toString()) > Double.valueOf(current.value.toString())) {
                    parent = current;
                    current = current.rightChild;
                    if (current == null) {
                        parent.rightChild = node;
                        break;
                    }
                } else {
                    error = "having same value in binary tree";
                }
            } // end of while
        }
        return error;
    }
}
